package org.example.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Administrator
 */
public class MovingCount {

    public static void main(String[] args) {
        int count = movingCount(1, 2, 1);
        System.out.println(count);
    }

    public static int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];

        return dfs(0, 0, m, n, visited, k);
    }

    private static int dfs(int i, int j, int m, int n, boolean[][] visited, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || (i % 10 + i / 10 + j % 10 + j / 10) > k) {
            return 0;
        }
        visited[i][j] = true;

        return dfs(i + 1, j, m, n, visited, k)
                + dfs(i - 1, j, m, n, visited, k)
                + dfs(i, j - 1, m, n, visited, k)
                + dfs(i, j + 1, m, n, visited, k)
                + 1;
    }
}
